package practic_2025_7_1;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 滑动窗口
 */
public class Solution {
    /**
     * 长度最小的子数组
     * @param target
     * @param nums
     * @return
     */
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0, right = 0;
        int len = nums.length;
        int res = Integer.MAX_VALUE;
        int sum = 0;
        while(right < len) {
            // 数据入窗口
            sum += nums[right];
            right++;
            // 数据出窗口
            while (sum >= target) {
                res = Math.min(res, right - left);
                sum -= nums[left++];
            }
        }
        return (res == Integer.MAX_VALUE ? 0: res);
    }

    /**
     * 水果成篮
     * @param fruits
     * @return
     */
    public int totalFruit(int[] fruits) {
        Map<Integer, Integer> hash = new HashMap<>();
        int res = 0;
        for(int left = 0, right = 0; right < fruits.length; right++) {
            hash.put(fruits[right], hash.getOrDefault(fruits[right], 0) + 1);
            while(left < right && hash.size() > 2) {
                if (hash.get(fruits[left]) == 1) {
                    hash.remove(fruits[left]);
                } else {
                    hash.put(fruits[left], hash.get(fruits[left]) - 1);
                }
                left++;
            }
            res = Math.max(res, right - left + 1);
        }
        return res;
    }

    /**
     * 将 x 减到 0 的最小操作数
     * @param nums
     * @param x
     * @return
     */
    public int minOperations(int[] nums, int x) {
        long sum = 0;
        for(int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        long target = sum - x;
        if (target == 0) return nums.length;
        int res = 0;
        sum = 0;
        for(int left = 0, right = 0; right < nums.length; right++) {
            sum += nums[right];
            while(left < right && sum > target) {
                sum -= nums[left];
                left++;
            }
            if (sum == target) {
                res = Math.max(res, right - left + 1);
            }
        }
        //  System.out.println(res);
        if (res == 0) {
            return -1;
        } else {
            return nums.length - res;
        }
    }

    /**
     * 找到字符串中所有字母异位词
     * @param s
     * @param p
     * @return
     */
    public List<Integer> findAnagrams(String s, String p) {
        int[] hash1 = new int[26];
        int[] hash2 = new int[26];
        List<Integer> res = new ArrayList<>();
        for(char ch: p.toCharArray()) {
            hash1[ch - 'a']++;
        }
        for(int left = 0, right = 0, count = 0; right < s.length(); right++) {
            // 入窗口
            int in = s.charAt(right) - 'a';
            hash2[in]++;
            if (hash2[in] <= hash1[in]) {
                count++;
            }
            // 出窗口判断
            if (right - left + 1 > p.length()) {
                int out = s.charAt(left) - 'a';
                if (hash2[out] <= hash1[out]) {
                    count--;
                }
                hash2[out]--;
                left++;
            }
            if (right - left + 1 == p.length() && count == p.length()) {
                res.add(left);
            }
        }
        return res;
    }

    /**
     * 最小覆盖子串
     * @param s
     * @param t
     * @return
     */
    public String minWindow(String s, String t) {
        int slen = s.length();
        int tlen = t.length();
        if (slen < tlen) return "";
        int begin = -1, len = slen + 1;
        int[] hash1 = new int[128];
        int[] hash2 = new int[128];
        for(char ch: t.toCharArray()) {
            hash1[ch]++;
        }
        for(int left = 0, right = 0, count =  0; right < slen; right++) {
            int in = s.charAt(right);
            hash2[in]++;
            if (hash2[in] <= hash1[in]) {
                count++;
            }
            while (count == tlen) {
                if (right - left + 1 < len) {
                    len = right - left + 1;
                    begin = left;
                }
                int out = s.charAt(left);
                if (hash2[out] <= hash1[out]) {
                    count--;
                }
                hash2[out]--;
                left++;
            }
        }
        if (begin == -1) {
            return "";
        } else {
            return s.substring(begin, begin + len);
        }
    }

    /**
     * 串联所有单词的子串
     * @param s
     * @param words
     * @return
     */
    public List<Integer> findSubstring(String s, String[] words) {
        int wordLen = words[0].length();
        Map<String, Integer> hash1 = new HashMap<>();
        for(String word: words) {
            hash1.put(word, hash1.getOrDefault(word, 0) + 1);
        }
        List<Integer> res = new ArrayList<>();
        for(int i = 0; i < wordLen; i++) {
            Map<String, Integer> hash2 = new HashMap<>();
            for(int left = i, right = i, count = 0; right + wordLen - 1 < s.length(); right += wordLen) {
                String in = s.substring(right, right + wordLen);
                hash2.put(in, hash2.getOrDefault(in, 0) + 1);
                //    System.out.println("in: " + in);
                if (hash2.getOrDefault(in, 0) <= hash1.getOrDefault(in, 0)) {
                    count++;
                }
                while(right - left + 1 > words.length * wordLen) {
                    String out = s.substring(left, left + wordLen);
                    if (hash2.getOrDefault(out, 0) <= hash1.getOrDefault(out, 0)) {
                        //   System.out.println("out: " + out + " hash1: " + hash1.get(out) + " hash2: " + hash1.get(out));
                        count--;
                    }
                    hash2.put(out, hash2.get(out) - 1);
                    left += wordLen;
                }
                //         System.out.println(left + " " + (right + wordLen - left) + " " + count);
                if (right + wordLen - left == wordLen * words.length && count == words.length) {
                    res.add(left);
                }
            }
        }
        return res;
    }
}
